package com.zx._12_算法.数据结构.queue;

import com.zx._12_算法.数据结构.stack.Stack;

/**
 * @version v1.0
 * @Project: knowledge
 * @Title: Queue2 用两个栈实现一个队列
 *         栈是先进后出，队列是先进先出，但可以用两个栈来模拟一个队列，请实现enqueue，dequeue， head这三个方法
 * @author: zhangxue
 * @date: 2019年7月23日下午10:48:36
 * @company: 未知之地
 * @Copyright: Copyright (c) 2019
 */
public class Queue2 {

    // 保存入栈的数据
    Stack<Integer> s1 = new Stack<Integer>();

    // 保存出栈的数据
    Stack<Integer> s2 = new Stack<Integer>();

    public void enqueue(Integer num) {
        s1.push(num);
    }

    public Integer dequeue() {
        // 两个栈都是空的
        if (s1.isEmpty() && s2.isEmpty()) {
            return null;
        }

        // 如果s2 是空的,那么s1一定不为空,把s1中的元素全部倒入s2
        // 这样s2中的数据与s1中数据插入的顺序是相反的。当s2全都取出的时候，再从s1中获得全部数据。
        if (s2.isEmpty()) {
            while (!s1.isEmpty()) {
                s2.push(s1.pop());
            }
        }
        // 取数据的时候从s2中取
        return s2.pop();
    }

}
